package bintree.newcoder;

import java.util.Scanner;

class TreeNode{
    public TreeNode(char val) {
        this.val = val;
    }

    char val;
    TreeNode left;
    TreeNode right;

}
public class Main {
    private static int index = 0;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String str = scanner.nextLine();
            TreeNode root = preOrderbuild(str);
            inOrde(root);
            System.out.println();
            index = 0;
        }
    }

    private static void inOrde(TreeNode root) {
        if (root==null){
            return;
        }
        inOrde(root.left);
        System.out.print(root.val+" ");
        inOrde(root.right);
    }

    private static TreeNode preOrderbuild(String str) {
        char cur = str.charAt(index);
        if (cur == '#'){
            return null;
        }
        TreeNode root = new TreeNode(cur);
        index++;
        root.left = preOrderbuild(str);
        index++;
        root.right=preOrderbuild(str);
        return root;
    }
}
